package simple;

/**
 * 给你一个排序后的字符列表 letters ，列表中只包含小写英文字母。另给出一个目标字母target，
 * 请你寻找在这一有序列表里比目标字母大的最小字母。
 *
 * 在比较时，字母是依序循环出现的。举个例子：
 *
 * 如果目标字母 target = 'z' 并且字符列表为resultletters = ['a', 'b']，则答案返回result'a'
 *
 * 链接：https://leetcode-cn.com/problems/find-smallest-letter-greater-than-target
 * @author 胡宇轩
 * @Email: yuxuan.hu01@bianlifeng.com
 */
public class FindSmallestLetterGreaterThanTarget {
    /**
     * 16:52 ~ 17:22 30min
     * 跟 最近的k个数字 不是一道题目吗？
     * 思想上 差不多类似的
     * */
    class Solution {
        public char nextGreatestLetter(char[] letters, char target) {
            if(target < letters[0] || target > letters[letters.length-1]){
                return letters[0];
            }
            else{
                int index = binarySearch(letters, (char) (target+1));
                return letters[index] > target ? letters[index] : letters[(index+1) % letters.length];
            }
        }

        int binarySearch(char[] letters, char target){
            int l = 0;
            int r = letters.length-1;
            while(l < r){
                int mid = l + (r - l) / 2;
                if(target > letters[mid]){
                    l = mid + 1;
                }else{
                    r = mid;
                }
            }
            return l;
        }
    }
}
